package com.mamingchao.foundation.arraysort.insertsort;

import com.mamingchao.foundation.arraysort.Sortable;

/**
 * 基于InsertSortV2实现，每次选择两个element 进行插入
 *
 * 此类的实现，每次选择待排序的element，选择两个。
 *
 * Created by mamingchao on 2020/11/13.
 */
public class PairInsertSortImpl implements Sortable{

    @Override
    public void sort(int[] arr, int start, int end) {
        // check arg array

        if (arr == null || arr.length <2) {
            return;
        }
        int i = 1;

        while (i < arr.length) {
            int temp = arr[i];
            int pos = binarySearch(arr,temp,0,i-1);
            if (i != pos) {
                for (int j = i ; j >pos; j--) {
                    //if the element is smaller than the previous element, then swap
                    arr[j] = arr[j-1];
                }
                arr[pos] = temp;
            }

            if (i !=arr.length -1) {
                int temp1 = arr[i+1];
                int pos1 = 0;
                if (temp1 > temp) {
                    pos1 = binarySearch(arr,temp1,pos+1,i);
                }else if (temp1 < temp) {
                    pos1 = binarySearch(arr,temp1,0,pos);
                } else {
                    pos1 = pos;
                }

                if (i+1 != pos1) {
                    for (int j = i+1 ; j >pos1; j--) {
                        //if the element is smaller than the previous element, then swap
                        arr[j] = arr[j-1];
                    }
                    arr[pos1] = temp1;
                }
            }
            i+=2;
        }
    }

    /**
     * arr 是已然排好序 的数组。value 值通过 二分法查找到 需要的数组索引位置 并返回
     * left 与 right 都是闭区间
     * @param arr
     * @param value
     */
    private static int binarySearch(int[] arr, int value, int leftIndex, int rightIndex) {

        if (rightIndex <= leftIndex) {
            if (arr[leftIndex] <= value) {
                return leftIndex + 1;
            } else
                return leftIndex;
        }

        int mid = leftIndex + (rightIndex - leftIndex)/2;

        // 左侧继续寻找
        if (arr[mid] > value) {
            return binarySearch(arr,value,leftIndex,mid - 1);
        } else if(arr[mid] < value) {
            return binarySearch(arr,value,mid + 1,rightIndex);
        } else { //arr[mid] == value 的情况
            return mid;
        }
    }
}
